package com.itheima.window;

import java.util.HashMap;

public class LeetCode1297 {
    //给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数：
    //
    //子串中不同字母的数目必须小于等于 maxLetters 。
    //子串的长度必须大于等于 minSize 且小于等于 maxSize 。
    //思路：maxsize的字符串一定包含了minsize的字符串，所以minsize<=maxsize，因此只需找大小为minsize的子串
    //做法：使用HashMap记载字符串的种类和数量，使用长度26的数组记载a-z26个字母在窗口的数量

    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        HashMap<String ,Integer> strs = new HashMap<>();
        char[] ss = s.toCharArray();
        int ssNum[] = new int[26];
        int kinds = 0;
        int max = 0;
        int length = ss.length;

        for (int i = 0; i < length; i++) {
               //窗口开始进入
            int in = ss[i] - 'a';
            if(ssNum[in] == 0){
                kinds++;
            }
            ssNum[in]++;
            // 窗口还未形成
            if(i < minSize -1){
                continue;
            }
            //窗口已然形成
            if(kinds <= maxLetters){
                //获得当前字符串
                String str = s.substring(i-minSize+1,i+1);
                //添加进map
                strs.put(str,strs.containsKey(str)? strs.get(str)+1 : 1);
                //获得最大字符串个数
                max = Math.max(max,strs.get(str));
            }

            //移除左侧字符
            int out = ss[i - minSize + 1] - 'a';
            ssNum[out]--;
            if(ssNum[out] == 0){
                kinds--;
            }
        }
        return max;
    }
}
